#include "graph.hh"
#include "utilis.hh"
#include <limits.h>

using namespace std;

#define MAX_ATTEMPT 50

int FindV(int ** d, int l, list<int> * R, int & v, int & i) {
	v = -1;
	i = l-1; // mayor diametro
	int d_i_v = INT_MAX;

	for (int j = 0; j < l; j++) {
		for (list<int>::iterator it = R->begin(); it != R->end(); ++it) {
			if (d[j][*it] <= d_i_v  && (d_i_v != d[j][*it] || j <= i)) {
				v = *it;
				i = j;
				d_i_v = d[j][*it];
			}
		}
	}

	//cout << "v, i: " << v+1 << " " << i << endl;

	if (v == -1) return -1; // nunca deberia llegar aca
	return 0;
}

int FindI(int ** d, int l, int dst) {
	int i = - 1;
	int d_i_dst = INT_MAX;
	for (int j = 0; j < l; j++) {
		if(d[j][dst] < d_i_dst && (d[j][dst] != d_i_dst || j <= i)) {
			d_i_dst = d[j][dst];
			i = j;
		}
	}

	return i;
}


Path * RestrictedShortestPath(Graph * Gp, int src, int dst, int l) {
	list<int> * U = new list<int>();
	list<int> * R = new list<int>();
	int ** d = new int*[l];
	int ** ant = new int*[l];
	int v;
	int di;

	//cout << "RSP ///////////////////////////" << endl;
	//// cout << "Inicializacoin " << endl;
	for (int i = 0; i < l; i++) {
		ant[i] = new int[Gp->sizeG];
		d[i] = new int[Gp->sizeG];

		for (int j = 0; j < Gp->sizeG; j++) {

			if (i==0 && Gp->actived_node[j] && j != src)
				U->push_front(j);

			if (i==0 && Gp->actived_node[j] && GetMatrix(Gp->E, src, j))
				R->push_front(j);

			if(Gp->actived_node[j]) {
				if (j == src) {
					d[i][j] = 0;
					ant[i][j] = -1;
				} else if (GetMatrix(Gp->E, src, j)) {
					d[i][j] = GetMatrix(Gp->C, src, j) + Gp->W[src] + Gp->W[j];
					ant[i][j] = src;
				} else {
					d[i][j] = INT_MAX;
					ant[i][j] = -1;
				}
			}
		}
	}

	/*// cout << "D " << endl;
	for (int i = 0; i < l; i++)
	{
		for (int j = 0; j < Gp->sizeG; j++)
			// cout << d[i][j] << " ";
		// cout << endl;
	}
	// cout << endl;


	// cout << "ANT " << endl;
	for (int i = 0; i < l; i++)
	{
		for (int j = 0; j < Gp->sizeG; j++)
			// cout << ant[i][j] << " ";
		// cout << endl;
	}
	// cout << endl;

	// cout << "R " << endl;
	for (list<int>::iterator it=R->begin(); it != R->end(); ++it)
		// cout << *it << " ";
	// cout << endl;

	// cout << "U " << endl;
	for (list<int>::iterator it=U->begin(); it != U->end(); ++it)
		// cout << *it << " ";
	// cout << endl;*/

	//// cout << "FIN Inicializacoin " << endl;



	//cout << "Busqueda " << endl;

	while (!R->empty() && 1 < l) {

		if (FindV(d, l, R, v, di)) {
			return new Path();
		}

	//	while(true);
		U->remove(v);
		R->remove(v);
		list<int> * neighbors = Gp->GetNeighbors(v, U);

		for (list<int>::iterator itw = neighbors->begin(); itw != neighbors->end(); ++itw) {
			for (int j = di + 1; j < l; j++) {
				if ((d[j - 1][v] < INT_MAX) && ((d[j - 1][v] + GetMatrix(Gp->C, v, *itw) + Gp->W[*itw]) <= d[j][*itw])) {
					d[j][*itw] = d[j - 1][v] + GetMatrix(Gp->C, v, *itw) + Gp->W[*itw];
					ant[j][*itw] = v;
				}
			}

			if (d[l-1][*itw] < INT_MAX) {
				if(R->end() == find(R->begin(), R->end(), *itw)) R->push_back(*itw);
			}
		}


		/*for(int i =0; i<l; i++) {
			cout << d[i][dst] << "  ";
			cout << endl;

		}*/

		/*if (v+1==24 || v+1 == 27 || v+1== 1 || v+1==56 || v+1==52) {


			cout << "N   "<< v+1 << "  " << di << endl;
			for (list<int>::iterator it=neighbors->begin(); it != neighbors->end(); ++it)
				cout << *it+1 << " ";
			cout << endl;

			cout << "R " << endl;
			for (list<int>::iterator it=R->begin(); it != R->end(); ++it)
				cout << *it+1 << " ";
			cout << endl;

			cout << "U " << endl;
			for (list<int>::iterator it=U->begin(); it != U->end(); ++it)
				cout << *it+1 << " ";
			cout << endl;


			for(int i =0; i<l; i++) {
				cout << d[i][v] << "  ";
				cout << endl;
			}

			int entero;
			cin >> entero;
		}*/

		DeleteListInt(neighbors);

	}
	//cout << "FIN Busqueda " << endl;


	//cout << "Armado " << endl;
	Path * path = new Path();

	int aux_i = FindI(d, l, dst);
	//cout << "di: " << aux_i <<endl;
	if(aux_i > -1) {
		int j = dst;
		while(ant[aux_i][j]>=0) {
			path->path->push_front(j);
			j = ant[aux_i][j];
		}
		path->path->push_front(src);
	}

	//// cout << "Path " << endl;
	//PrintGraph2(path);
	//cout << "Fin Armado " << endl;

	DeleteMatrix(ant, l);
	DeleteMatrix(d, l);
	U->clear();
	R->clear();
	delete U;
	delete R;

	return path;
}

list<Path*> * Graph::GetKPathsBetween(int src, int dst, int k, int l) {

	list<Path*> * paths = new list<Path*>();
	Path * 	path;
	int attemp = 0;
	list<pair<int, int>* > * edges = new list<pair<int, int>* >();
	pair<int, int>* edge;


	/*for(int i=0; i< k; i++)
	{
		path = RestrictedShortestPath(this, src, dst, l);
		paths->push_front(path);
	}*/

	while(paths->size() < (unsigned int) k && attemp < MAX_ATTEMPT) {
		//cout << "RSP ///////////////////////////     " << attemp << endl;
		path = RestrictedShortestPath(this, src, dst, l);
		//cout << "FIN RSP ///////////////////////     " << attemp << endl;

		//path = new Path();

		if(path->IsEmpty()) {
			delete path;
			attemp++;

			for (list<pair<int, int>*>::iterator it = edges->begin(); it != edges->end(); ++it) { // habilito las aristas de nuevo
				SetMatrix(E, (*it)->first, (*it)->second, 1);
			}

			CleanListPairInt(edges);

			for (list<Path *>::iterator it = paths->begin(); it != paths->end(); ++it) { // deshabilito nuevas aristas para volver a intentar
				edge = RandomEdge(*it);
				edges->push_front(edge);
				SetMatrix(E, edge->first, edge->second, 0);
			}
		}
		else {
			paths->push_front(path);
			edge = RandomEdge(path);
			edges->push_front(edge);
			//// cout << "Edge " << "(" << edge->first << ", " << edge->second << ")"<<endl;
			SetMatrix(E, edge->first, edge->second, 0); // inablito la arista, para que el RSP no encuntre el mismo camino
		}
	}

	for (list<pair<int, int>*>::iterator it = edges->begin(); it != edges->end(); ++it) { // habilito las aristas de nuevo
		SetMatrix(E, (*it)->first, (*it)->second, 1);
	}

	DeleteListPairInt(edges);
	//if(paths->size() < k) cout << "[GetKPathsBetween][INFO]: less k " << paths->size() << endl;

	return paths;
}
